package org.example.myleet.p828;

/*
  参考题解：https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/solution/tong-ji-zi-chuan-zhong-de-wei-yi-zi-fu-b-ajio/
 */

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int uniqueLetterString(String s) {
        Map<Character, Integer> lastIdxMap = new HashMap<>();
        Map<Character, Integer> curIdxMap = new HashMap<>();
        int res = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            int lastIdx = lastIdxMap.getOrDefault(c, -1);
            int curIdx = curIdxMap.getOrDefault(c, -1);
            if (-1 < curIdx) {
                res += (curIdx - lastIdx) * (i - curIdx);
            }
            lastIdxMap.put(c, curIdx);
            curIdxMap.put(c, i);
        }
        //计算最后next字符的贡献值，最后一个位置就是s.length()
        for (Map.Entry<Character, Integer> entry : curIdxMap.entrySet()) {
            res += (entry.getValue() - lastIdxMap.get(entry.getKey())) * (s.length() - entry.getValue());
        }
        return res;
    }
}
